CF398B Painting The Wall

先考虑所有格子均未涂色的情况。

因为格子的涂色只会影响一行一列,所以可以设 dp(i,j)dp(i,j) 表示还需要涂 ii 行 , jj 列的期望步数。

1.涂色格所在行列均未染色,由 dp(i1,j1)dp(i-1,j-1) 转移,概率为 in×jn\frac{i}{n} \times \frac{j}{n}

2.涂色格所在行未染色,列已染色,由 $dp(i-1,j) $ 转移,概率为 in×njn\frac{i}{n} \times \frac{n-j}{n}

3.涂色格所在列未染色,行已染色,由 $dp(i,j-1) $ 转移,概率为 nin×jn\frac{n-i}{n} \times \frac{j}{n}

4.涂色格所在行列均已染色,由 dp(i,j)dp(i,j) 转移,概率为 nin×njn\frac{n-i}{n} \times \frac{n-j}{n}

综上得:

dp(i,j)=1+dp(i1,j)i(nj)n2+dp(i,j1)(ni)jn2+dp(i1,j1)ijn2+dp(i,j)(ni)(nj)n2dp(i,j) = 1 + dp( i - 1 , j ) * \frac{i * ( n - j )}{n^2} + dp( i , j - 1 ) * \frac{( n - i ) * j}{n^2} + dp( i - 1 , j - 1 ) * \frac{i * j}{n^2} + dp(i,j) * \frac{(n-i)*(n-j)}{n^2}

移项得:

dp(i,j)=1+dp(i1,j)i(nj)n2+dp(i,j1)(ni)jn2+dp(i1,j1)ijn21(ni)(nj)n2dp(i,j) = \frac{ 1 + dp( i - 1 , j ) * \frac{i * ( n - j )}{n^2} + dp( i , j - 1 ) * \frac{( n - i ) * j}{n^2} + dp( i - 1 , j - 1 ) * \frac{i * j}{n^2} }{1-\frac{(n-i)(n-j)}{n^2}}

上下同时乘 n2n^2 得到:

dp(i,j)=n2+dp(i1,j)i(nj)+dp(i,j1)(ni)j+dp(i1,j1)ijn2(ni)(nj)dp(i,j) = \frac{ n^2 + dp( i - 1 , j ) * i * ( n - j ) + dp( i , j - 1 ) * ( n - i ) * j + dp( i - 1 , j - 1 ) * i * j }{n^2-(n-i)(n-j)}

边界条件:

1.dp[0][0]=0dp[0][0]=0

2.dp[0][i]/dp[i][0]=j=1iijdp[0][i]/dp[i][0]=\sum_{j=1}^i \lfloor \frac{i}{j} \rfloor 经典的邮票收集问题

现在再考虑一开始有涂色的格子,其实只是让其中一些行列提前满足要求,即答案并不是 dp(n,n)dp(n,n) ,而是减去已满足数量的结果自己意会一下

#include <cstdio>

const int MAXN = 2e3;
int n , m , x , y;
bool vis[ 2 ][ MAXN + 5 ];
double dp[ MAXN + 5 ][ MAXN + 5 ];

int main( ) {
	scanf("%d %d",&n,&m);
	for( int i = 1 , u , v ; i <= m ; i ++ ) {
		scanf("%d %d",&u,&v);
		if( !vis[ 0 ][ u ] ) x -= ( vis[ 0 ][ u ] = 1 );
		if( !vis[ 1 ][ v ] ) y -= ( vis[ 1 ][ v ] = 1 );
	}
	x += n , y += n;

	dp[ 0 ][ 0 ] = 0;
	for( int i = 1 ; i <= n ; i ++ ) {
		dp[ i ][ 0 ] = dp[ i - 1 ][ 0 ] + n * 1.0 / i;
		dp[ 0 ][ i ] = dp[ 0 ][ i - 1 ] + n * 1.0 / i;
	}
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= n ; j ++ )
			dp[ i ][ j ] = ( n * n + dp[ i - 1 ][ j ] * i * ( n - j ) + dp[ i ][ j - 1 ] * ( n - i ) * j + dp[ i - 1 ][ j - 1 ] * i * j ) / ( n * n - ( n - i ) * ( n - j ) );

	printf("%.10f", dp[ x ][ y ] );
	return 0;
}